class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return qsort(nums,0,nums.size()-1,k);
    }

    int qsort(vector<int>& nums,int begin,int end,int k)
    {
        //进了这个区间一定能找到
        if(begin>=end)return nums[begin];

        int key=nums[begin];
        int left=begin;
        int right=end;

        int cur=left+1;
        //分成三块
        while(cur<=right)
        {
            if(nums[cur]<key)
            {
                swap(nums[left++],nums[cur++]);
            }
            else if(nums[cur]==key)
            {
                cur++;
            }
            else
            {
                swap(nums[right--],nums[cur]);
            }
        }
        int c=end-right;
        int b=right-left+1;
        if(c>=k)return qsort(nums,right+1,end,k);
        else if(b+c>=k)return key;
        else return qsort(nums,begin,left-1,k-b-c);
    }
};